home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / tjunction.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  12.2 KB  |  531 lines
  1. #include "qbsp.h"
  2.  
  3. typedef struct edgePoint_s {
  4.     float        intercept;
  5.     vec3_t        xyz;
  6.     struct edgePoint_s    *prev, *next;
  7. } edgePoint_t;
  8.  
  9. typedef struct edgeLine_s {
  10.     vec3_t        normal1;
  11.     float        dist1;
  12.     
  13.     vec3_t        normal2;
  14.     float        dist2;
  15.     
  16.     vec3_t        origin;
  17.     vec3_t        dir;
  18.  
  19.     edgePoint_t    chain;        // unused element of doubly linked list
  20. } edgeLine_t;
  21.  
  22. typedef struct {
  23.     float        length;
  24.     drawVert_t    *dv[2];
  25. } originalEdge_t;
  26.  
  27. #define    MAX_ORIGINAL_EDGES    0x10000
  28. originalEdge_t    originalEdges[MAX_ORIGINAL_EDGES];
  29. int                numOriginalEdges;
  30.  
  31.  
  32. #define    MAX_EDGE_LINES        0x10000
  33. edgeLine_t        edgeLines[MAX_EDGE_LINES];
  34. int                numEdgeLines;
  35.  
  36. int                c_degenerateEdges;
  37. int                c_addedVerts;
  38. int                c_totalVerts;
  39.  
  40. int                c_natural, c_rotate, c_cant;
  41.  
  42. // these should be whatever epsilon we actually expect,
  43. // plus SNAP_INT_TO_FLOAT 
  44. #define    LINE_POSITION_EPSILON    0.25
  45. #define    POINT_ON_LINE_EPSILON    0.25
  46.  
  47. /*
  48. ====================
  49. InsertPointOnEdge
  50. ====================
  51. */
  52. void InsertPointOnEdge( vec3_t v, edgeLine_t *e ) {
  53.     vec3_t        delta;
  54.     float        d;
  55.     edgePoint_t    *p, *scan;
  56.  
  57.     VectorSubtract( v, e->origin, delta );
  58.     d = DotProduct( delta, e->dir );
  59.  
  60.     p = malloc( sizeof(edgePoint_t) );
  61.     p->intercept = d;
  62.     VectorCopy( v, p->xyz );
  63.  
  64.     if ( e->chain.next == &e->chain ) {
  65.         e->chain.next = e->chain.prev = p;
  66.         p->next = p->prev = &e->chain;
  67.         return;
  68.     }
  69.  
  70.     scan = e->chain.next;
  71.     for ( ; scan != &e->chain ; scan = scan->next ) {
  72.         d = p->intercept - scan->intercept;
  73.         if ( d > -LINE_POSITION_EPSILON && d < LINE_POSITION_EPSILON ) {
  74.             free( p );
  75.             return;        // the point is already set
  76.         }
  77.  
  78.         if ( p->intercept < scan->intercept ) {
  79.             // insert here
  80.             p->prev = scan->prev;
  81.             p->next = scan;
  82.             scan->prev->next = p;
  83.             scan->prev = p;
  84.             return;
  85.         }
  86.     }
  87.  
  88.     // add at the end
  89.     p->prev = scan->prev;
  90.     p->next = scan;
  91.     scan->prev->next = p;
  92.     scan->prev = p;
  93. }
  94.  
  95.  
  96. /*
  97. ====================
  98. AddEdge
  99. ====================
  100. */
  101. int AddEdge( vec3_t v1, vec3_t v2, qboolean createNonAxial ) {
  102.     int            i;
  103.     edgeLine_t    *e;
  104.     float        d;
  105.     vec3_t        dir;
  106.  
  107.     VectorSubtract( v2, v1, dir );
  108.     d = VectorNormalize( dir, dir );
  109.     if ( d < 0.1 ) {
  110.         // if we added a 0 length vector, it would make degenerate planes
  111.         c_degenerateEdges++;
  112.         return -1;
  113.     }
  114.  
  115.     if ( !createNonAxial ) {
  116.         if ( fabs( dir[0] + dir[1] + dir[2] ) != 1.0 ) {
  117.             if ( numOriginalEdges == MAX_ORIGINAL_EDGES ) {
  118.                 Error( "MAX_ORIGINAL_EDGES" );
  119.             }
  120.             originalEdges[ numOriginalEdges ].dv[0] = (drawVert_t *)v1;
  121.             originalEdges[ numOriginalEdges ].dv[1] = (drawVert_t *)v2;
  122.             originalEdges[ numOriginalEdges ].length = d;
  123.             numOriginalEdges++;
  124.             return -1;
  125.         }
  126.     }
  127.  
  128.     for ( i = 0 ; i < numEdgeLines ; i++ ) {
  129.         e = &edgeLines[i];
  130.  
  131.         d = DotProduct( v1, e->normal1 ) - e->dist1;
  132.         if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
  133.             continue;
  134.         }
  135.         d = DotProduct( v1, e->normal2 ) - e->dist2;
  136.         if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
  137.             continue;
  138.         }
  139.  
  140.         d = DotProduct( v2, e->normal1 ) - e->dist1;
  141.         if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
  142.             continue;
  143.         }
  144.         d = DotProduct( v2, e->normal2 ) - e->dist2;
  145.         if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {
  146.             continue;
  147.         }
  148.  
  149.         // this is the edge
  150.         InsertPointOnEdge( v1, e );
  151.         InsertPointOnEdge( v2, e );
  152.         return i;
  153.     }
  154.  
  155.     // create a new edge
  156.     if ( numEdgeLines >= MAX_EDGE_LINES ) {
  157.         Error( "MAX_EDGE_LINES" );
  158.     }
  159.  
  160.     e = &edgeLines[ numEdgeLines ];
  161.     numEdgeLines++;
  162.  
  163.     e->chain.next = e->chain.prev = &e->chain;
  164.  
  165.     VectorCopy( v1, e->origin );
  166.     VectorCopy( dir, e->dir );
  167.  
  168.     MakeNormalVectors( e->dir, e->normal1, e->normal2 );
  169.     e->dist1 = DotProduct( e->origin, e->normal1 );
  170.     e->dist2 = DotProduct( e->origin, e->normal2 );
  171.  
  172.     InsertPointOnEdge( v1, e );
  173.     InsertPointOnEdge( v2, e );
  174.  
  175.     return numEdgeLines - 1;
  176. }
  177.  
  178. /*
  179. ====================
  180. AddSurfaceEdges
  181. ====================
  182. */
  183. void AddSurfaceEdges( mapDrawSurface_t *ds ) {
  184.     int        i;
  185.  
  186.     for ( i = 0 ; i < ds->numVerts ; i++ ) {
  187.         // save the edge number in the lightmap field
  188.         // so we don't need to look it up again
  189.         ds->verts[i].lightmap[0] = 
  190.             AddEdge( ds->verts[i].xyz, ds->verts[(i+1) % ds->numVerts].xyz, qfalse );
  191.     }
  192. }
  193.  
  194. /*
  195. ================
  196. ColinearEdge
  197. ================
  198. */
  199. qboolean ColinearEdge( vec3_t v1, vec3_t v2, vec3_t v3 ) {
  200.     vec3_t    midpoint, dir, offset, on;
  201.     float    d;
  202.  
  203.     VectorSubtract( v2, v1, midpoint );
  204.     VectorSubtract( v3, v1, dir );
  205.     d = VectorNormalize( dir, dir );
  206.     if ( d == 0 ) {
  207.         return qfalse;    // degenerate
  208.     }
  209.  
  210.     d = DotProduct( midpoint, dir );
  211.     VectorScale( dir, d, on );
  212.     VectorSubtract( midpoint, on, offset );
  213.     d = VectorLength ( offset );
  214.  
  215.     if ( d < 0.1 ) {
  216.         return qtrue;
  217.     }
  218.  
  219.     return qfalse;
  220. }
  221.  
  222. /*
  223. ====================
  224. AddPatchEdges
  225.  
  226. Add colinear border edges, which will fix some classes of patch to
  227. brush tjunctions
  228. ====================
  229. */
  230. void AddPatchEdges( mapDrawSurface_t *ds ) {
  231.     int        i;
  232.     float    *v1, *v2, *v3;
  233.  
  234.     for ( i = 0 ; i < ds->patchWidth - 2; i+=2 ) {
  235.         v1 = ds->verts[ i ].xyz;
  236.         v2 = ds->verts[ i + 1 ].xyz;
  237.         v3 = ds->verts[ i + 2 ].xyz;
  238.  
  239.         // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
  240.         if ( ColinearEdge( v1, v2, v3 ) ) {
  241.             AddEdge( v1, v3, qfalse );
  242.         }
  243.  
  244.         v1 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i ].xyz;
  245.         v2 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 1 ].xyz;
  246.         v3 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 2 ].xyz;
  247.  
  248.         // if v2 is on the v1 to v3 line, add an edge from v1 to v3
  249.         if ( ColinearEdge( v1, v2, v3 ) ) {
  250.             AddEdge( v1, v3, qfalse );
  251.         }
  252.     }
  253.  
  254.     for ( i = 0 ; i < ds->patchHeight - 2 ; i+=2 ) {
  255.         v1 = ds->verts[ i * ds->patchWidth ].xyz;
  256.         v2 = ds->verts[ ( i + 1 ) * ds->patchWidth ].xyz;
  257.         v3 = ds->verts[ ( i + 2 ) * ds->patchWidth ].xyz;
  258.  
  259.         // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
  260.         if ( ColinearEdge( v1, v2, v3 ) ) {
  261.             AddEdge( v1, v3, qfalse );
  262.         }
  263.  
  264.         v1 = ds->verts[ ( ds->patchWidth - 1 ) + i * ds->patchWidth ].xyz;
  265.         v2 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 1 ) * ds->patchWidth ].xyz;
  266.         v3 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 2 ) * ds->patchWidth ].xyz;
  267.  
  268.         // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3
  269.         if ( ColinearEdge( v1, v2, v3 ) ) {
  270.             AddEdge( v1, v3, qfalse );
  271.         }
  272.     }
  273.  
  274.  
  275. }
  276.  
  277.  
  278. /*
  279. ====================
  280. FixSurfaceJunctions
  281. ====================
  282. */
  283. #define    MAX_SURFACE_VERTS    256
  284. void FixSurfaceJunctions( mapDrawSurface_t *ds ) {
  285.     int            i, j, k;
  286.     edgeLine_t    *e;
  287.     edgePoint_t    *p;
  288.     int            originalVerts;
  289.     int            counts[MAX_SURFACE_VERTS];
  290.     int            originals[MAX_SURFACE_VERTS];
  291.     int            firstVert[MAX_SURFACE_VERTS];
  292.     drawVert_t    verts[MAX_SURFACE_VERTS], *v1, *v2;
  293.     int            numVerts;
  294.     float        start, end, frac;
  295.     vec3_t        delta;
  296.  
  297.     originalVerts = ds->numVerts;
  298.  
  299.     numVerts = 0;
  300.     for ( i = 0 ; i < ds->numVerts ; i++ ) {
  301.         counts[i] = 0;
  302.         firstVert[i] = numVerts;
  303.  
  304.         // copy first vert
  305.         if ( numVerts == MAX_SURFACE_VERTS ) {
  306.             Error( "MAX_SURFACE_VERTS" );
  307.         }
  308.         verts[numVerts] = ds->verts[i];
  309.         originals[numVerts] = i;
  310.         numVerts++;
  311.  
  312.         // check to see if there are any t junctions before the next vert
  313.         v1 = &ds->verts[i];
  314.         v2 = &ds->verts[ (i+1) % ds->numVerts ];
  315.  
  316.         j = (int)ds->verts[i].lightmap[0];
  317.         if ( j == -1 ) {
  318.             continue;        // degenerate edge
  319.         }
  320.         e = &edgeLines[ j ];
  321.         
  322.         VectorSubtract( v1->xyz, e->origin, delta );
  323.         start = DotProduct( delta, e->dir );
  324.  
  325.         VectorSubtract( v2->xyz, e->origin, delta );
  326.         end = DotProduct( delta, e->dir );
  327.  
  328.  
  329.         if ( start < end ) {
  330.             p = e->chain.next;
  331.         } else {
  332.             p = e->chain.prev;
  333.         }
  334.  
  335.         for (  ; p != &e->chain ;  ) {
  336.             if ( start < end ) {
  337.                 if ( p->intercept > end - ON_EPSILON ) {
  338.                     break;
  339.                 }
  340.             } else {
  341.                 if ( p->intercept < end + ON_EPSILON ) {
  342.                     break;
  343.                 }
  344.             }
  345.  
  346.             if ( 
  347.                 ( start < end && p->intercept > start + ON_EPSILON ) ||
  348.                 ( start > end && p->intercept < start - ON_EPSILON ) ) {
  349.                 // insert this point
  350.                 if ( numVerts == MAX_SURFACE_VERTS ) {
  351.                     Error( "MAX_SURFACE_VERTS" );
  352.                 }
  353.  
  354.                 // take the exact intercept point
  355.                 VectorCopy( p->xyz, verts[ numVerts ].xyz );
  356.  
  357.                 // copy the normal
  358.                 VectorCopy( v1->normal, verts[ numVerts ].normal );
  359.  
  360.                 // interpolate the texture coordinates
  361.                 frac = ( p->intercept - start ) / ( end - start );
  362.                 for ( j = 0 ; j < 2 ; j++ ) {
  363.                     verts[ numVerts ].st[j] = v1->st[j] + 
  364.                         frac * ( v2->st[j] - v1->st[j] );
  365.                 }
  366.                 originals[numVerts] = i;
  367.                 numVerts++;
  368.                 counts[i]++;
  369.             }
  370.  
  371.             if ( start < end ) {
  372.                 p = p->next;
  373.             } else {
  374.                 p = p->prev;
  375.             }
  376.         }
  377.     }
  378.  
  379.     c_addedVerts += numVerts - ds->numVerts;
  380.     c_totalVerts += numVerts;
  381.  
  382.  
  383.     // FIXME: check to see if the entire surface degenerated
  384.     // after snapping
  385.  
  386.     // rotate the points so that the initial vertex is between
  387.     // two non-subdivided edges
  388.     for ( i = 0 ; i < numVerts ; i++ ) {
  389.         if ( originals[ (i+1) % numVerts ] == originals[ i ] ) {
  390.             continue;
  391.         }
  392.         j = (i + numVerts - 1 ) % numVerts;
  393.         k = (i + numVerts - 2 ) % numVerts;
  394.         if ( originals[ j ] == originals[ k ] ) {
  395.             continue;
  396.         }
  397.         break;
  398.     }
  399.  
  400.     if ( i == 0 ) {
  401.         // fine the way it is
  402.         c_natural++;
  403.  
  404.         ds->numVerts = numVerts;
  405.         ds->verts = malloc( numVerts * sizeof( *ds->verts ) );
  406.         memcpy( ds->verts, verts, numVerts * sizeof( *ds->verts ) );
  407.  
  408.         return;
  409.     }
  410.     if ( i == numVerts ) {
  411.         // create a vertex in the middle to start the fan
  412.         c_cant++;
  413.  
  414. /*
  415.         memset ( &verts[numVerts], 0, sizeof( verts[numVerts] ) );
  416.         for ( i = 0 ; i < numVerts ; i++ ) {
  417.             for ( j = 0 ; j < 10 ; j++ ) {
  418.                 verts[numVerts].xyz[j] += verts[i].xyz[j];
  419.             }
  420.         }
  421.         for ( j = 0 ; j < 10 ; j++ ) {
  422.             verts[numVerts].xyz[j] /= numVerts;
  423.         }
  424.  
  425.         i = numVerts;
  426.         numVerts++;
  427. */
  428.     } else {
  429.         // just rotate the vertexes
  430.         c_rotate++;
  431.  
  432.     }
  433.  
  434.     ds->numVerts = numVerts;
  435.     ds->verts = malloc( numVerts * sizeof( *ds->verts ) );
  436.  
  437.     for ( j = 0 ; j < ds->numVerts ; j++ ) {
  438.         ds->verts[j] = verts[ ( j + i ) % ds->numVerts ];
  439.     }
  440. }
  441.  
  442. /*
  443. ================
  444. EdgeCompare
  445. ================
  446. */
  447. int EdgeCompare( const void *elem1, const void *elem2 ) {
  448.     float    d1, d2;
  449.  
  450.     d1 = ((originalEdge_t *)elem1)->length;
  451.     d2 = ((originalEdge_t *)elem2)->length;
  452.  
  453.     if ( d1 < d2 ) {
  454.         return -1;
  455.     }
  456.     if ( d2 > d1 ) {
  457.         return 1;
  458.     }
  459.     return 0;
  460. }
  461.  
  462.  
  463. /*
  464. ================
  465. FixTJunctions
  466.  
  467. Call after the surface list has been pruned, but before lightmap allocation
  468. ================
  469. */
  470. void FixTJunctions( entity_t *ent ) {
  471.     int                    i;
  472.     mapDrawSurface_t    *ds;
  473.     int                    axialEdgeLines;
  474.     originalEdge_t        *e;
  475.  
  476.     qprintf("----- FixTJunctions -----\n");
  477.  
  478.     numEdgeLines = 0;
  479.     numOriginalEdges = 0;
  480.  
  481.     // add all the edges
  482.     // this actually creates axial edges, but it
  483.     // only creates originalEdge_t structures
  484.     // for non-axial edges
  485.     for ( i = ent->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) {
  486.         ds = &mapDrawSurfs[i];
  487.         if ( ds->patch ) {
  488.             AddPatchEdges( ds );
  489.         } else if ( ds->shaderInfo->autosprite || ds->shaderInfo->notjunc || ds->miscModel ) {
  490.             // miscModels don't add tjunctions
  491.         } else {
  492.             AddSurfaceEdges( ds );
  493.         }
  494.     }
  495.  
  496.     axialEdgeLines = numEdgeLines;
  497.  
  498.     // sort the non-axial edges by length
  499.     qsort( originalEdges, numOriginalEdges, sizeof(originalEdges[0]), EdgeCompare );
  500.  
  501.     // add the non-axial edges, longest first
  502.     // this gives the most accurate edge description
  503.     for ( i = 0 ; i < numOriginalEdges ; i++ ) {
  504.         e = &originalEdges[i];
  505.         e->dv[0]->lightmap[0] = AddEdge( e->dv[0]->xyz, e->dv[1]->xyz, qtrue );
  506.     }
  507.  
  508.     qprintf( "%6i axial edge lines\n", axialEdgeLines );
  509.     qprintf( "%6i non-axial edge lines\n", numEdgeLines - axialEdgeLines );
  510.     qprintf( "%6i degenerate edges\n", c_degenerateEdges );
  511.  
  512.     // insert any needed vertexes
  513.     for ( i = ent->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) {
  514.         ds = &mapDrawSurfs[i];
  515.         if ( ds->patch ) {
  516.             continue;
  517.         }
  518.         if ( ds->shaderInfo->autosprite || ds->shaderInfo->notjunc || ds->miscModel ) {
  519.             continue;
  520.         }
  521.  
  522.         FixSurfaceJunctions( ds );
  523.     }
  524.  
  525.     qprintf( "%6i verts added for tjunctions\n", c_addedVerts );
  526.     qprintf( "%6i total verts\n", c_totalVerts );
  527.     qprintf( "%6i naturally ordered\n", c_natural );
  528.     qprintf( "%6i rotated orders\n", c_rotate );
  529.     qprintf( "%6i can't order\n", c_cant );
  530. }
  531.